import java.util.Arrays;
import java.util.Objects;
import java.util.Stack;

public class Mystack {
     public int[] elem;
     public int usedsize;

    public Mystack() {
        elem = new int[10];
    }

    public void push(int val){
        if(isFull()){
            elem = Arrays.copyOf(elem,2*elem.length);
        }
    }
    private boolean isFull(){
        return elem.length == usedsize;
    }
    public int pop(){
        if(isEmpty()){
            throw new PopIndexException();
        }
        int val = elem[usedsize - 1];
        usedsize--;
        return val;
    }

    private boolean isEmpty(){
        return size() == 0;
    }
    public int peek(){
        if(isEmpty()){
            throw new PopIndexException();
        }
        return elem[usedsize - 1];
    }
    public int size(){
        return usedsize;
    }

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);

            if(ch == '(' || ch == '[' || ch == '{'){
                stack.push(ch);
            }else{
                if(stack.isEmpty()){
                    return false;
                }
                if((ch == ')'&& stack.peek() == '(') ||
                        (ch == ']' && stack.peek() == '[')||
                        (ch == '}' && stack.peek() == '{')){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        if(stack.isEmpty()){
            return true;
        }
        return false;
    }

    public int evalRPN(String[] tokens) {
        Stack<Integer> stack  = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {

            if((Objects.equals(tokens[i], "+")) || (Objects.equals(tokens[i], "-")) || (Objects.equals(tokens[i], "*")) ||(Objects.equals(tokens[i], "/")) ){
                int b = stack.pop();
                int a = stack.pop();
                switch(tokens[i]){
                    case"+":
                        stack.push(a + b);
                        break;
                    case"-":
                        stack.push(a - b);
                        break;
                    case"*":
                        stack.push(a * b);
                        break;
                    case"/":
                        stack.push(a / b);
                        break;
                }
            }else{
                stack.push(Integer.parseInt(tokens[i]));
            }
        }
        return stack.pop();
    }
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        int j = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < pushV.length; i++) {
            stack.push(pushV[i]);
            while(!stack.isEmpty()){
                if(stack.peek().equals(popV[j])){
                    stack.pop();
                    j++;
                }else{
                    break;
                }
            }

        }
        while(!stack.isEmpty()){
            if(stack.peek().equals(popV[j])){
                stack.pop();
                j++;
            }else{
                return false;
            }
            if(j == popV.length){
                if(!stack.isEmpty()){
                    return false;
                }
            }
        }

        return true;
    }
}
